package Leetcode.树;

/**
 * @ClassName 二叉树的最近公共祖先
 * @since: 2023/8/19 11:53
 * @auth: kirito
 * @description:
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，
 * 最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大
 * （一个节点也可以是它自己的祖先）。”
 **/
public class 二叉树的最近公共祖先 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果根节点为空或者根节点等于p或q，则返回根节点
        if (root == null || root == p || root == q) {
            return root;
        }
        // 在左子树中寻找p和q的最近公共祖先
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 在右子树中寻找p和q的最近公共祖先
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 如果左子树和右子树的结果都不为空，说明p和q分别位于当前节点的左右子树中，当前节点即为最近公共祖先
        if (left != null && right != null) {
            return root;
        }
        // 如果左子树的结果不为空，说明p和q都在左子树中，返回左子树的结果作为最近公共祖先
        return left != null ? left : right;
    }

}
